package demo5;
import com.sun.org.apache.xpath.internal.axes.AttributeIterator;
import javafx.util.Pair;
import java.util.*;
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
public class Solution {
//    //1.电话号码的字母组合
//    private void dfs(String digits, List<String> list,
//                     StringBuilder path, int digitsIndex) {
//        if(digitsIndex == digits.length()) {
//            list.add(new String(path));
//            return;
//        }
//        int num = digits.charAt(digitsIndex) - '0';
//        String str = map[num];
//        for(int i = 0; i < str.length(); i++) {
//            path.append(str.charAt(i));
//            dfs(digits, list, path, digitsIndex + 1);
//            path.deleteCharAt(path.length() - 1);
//        }
//    }
//
//    String[] map = { " ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//    public List<String> letterCombinations(String digits) {
//        List<String> list = new ArrayList<>();//用来存放所有可能
//        if(digits.length() == 0) {
//            return list;
//        }
//        StringBuilder path = new StringBuilder();//用来存放每一种组合的可能
//        dfs(digits, list, path, 0);
//        return list;
//    }

//    //2.组合总数
//    private void dfs(int[] candidates, int target, List<Integer> path, int sum) {
//        if(sum == target) {
//            list.add(new ArrayList<>(path));
//            return;
//        } else if(sum > target) {
//            return;
//        }
//        for(int i = 0; i < candidates.length; i++) {
//            //保证同一个组合不会出现多次
//            if(!path.isEmpty() && path.get(path.size() - 1) > candidates[i]) {
//                continue;
//            }
//            path.add(candidates[i]);
//            dfs(candidates, target, path, sum + candidates[i]);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private List<List<Integer>> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        List<Integer> path = new ArrayList<>();
//        dfs(candidates, target, path, 0);
//        return list;
//    }

//    //2.组合总数(优化)
//    private void dfs(int[] candidates, int target, List<Integer> path, int sum) {
//        if(sum == target) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = 0; i < candidates.length; i++) {
//            if(sum + candidates[i] > target) {//已经大于了就没必要再往后看了
//                continue;
//            }
//            //保证同一个组合不会出现多次
//            if(!path.isEmpty() && path.get(path.size() - 1) > candidates[i]) {
//                continue;
//            }
//            path.add(candidates[i]);
//            dfs(candidates, target, path, sum + candidates[i]);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private List<List<Integer>> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        List<Integer> path = new ArrayList<>();
//        dfs(candidates, target, path, 0);
//        return list;
//    }

//    //这里的start参数是保证顺序，避免重复解
//    private void dfs(int[] candidates, int target, List<Integer> path, int sum, int start) {
//        if(sum == target) {
//            list.add(new ArrayList<>(path));
//            return;
//        }
//        for(int i = start; i < candidates.length; i++) {
//            if(sum + candidates[i] > target) {//已经大于了就没必要再往后看了
//                continue;
//            }
//            path.add(candidates[i]);
//            dfs(candidates, target, path, sum + candidates[i], i);
//            path.remove(path.size() - 1);
//        }
//    }
//
//    private List<List<Integer>> list = new ArrayList<>();
//    public List<List<Integer>> combinationSum(int[] candidates, int target) {
//        List<Integer> path = new ArrayList<>();
//        dfs(candidates, target, path, 0, 0);
//        return list;
//    }
//    //3.活字印刷(回溯 + dfs)
//    private void dfs(String tiles, boolean[] flag, StringBuilder path) {
//        if(path.length() != 0) {
//            set.add(path.toString());
//        }
//        for(int i = 0; i < tiles.length(); i++) {
//            if(!flag[i]) {
//                flag[i] = true;
//                path.append(tiles.charAt(i));
//                dfs(tiles, flag, path);
//                path.deleteCharAt(path.length() - 1);
//                flag[i] = false;
//            }
//        }
//    }
//    private Set<String> set = new HashSet<>();
//    public int numTilePossibilities(String tiles) {
//
//        StringBuilder path = new StringBuilder();
//        boolean[] flag = new boolean[tiles.length()];
//        dfs(tiles, flag, path);
//        return set.size();
//    }

//
//    private void dfs(Map<Integer, Integer> path, List<Map<Integer, Integer>> location, int row, int n) {
//        if(row == n) {
//            location.add(new HashMap<>(path));
//            return;
//        }
//        //看每一列是否可行
//        for(int i = 0; i < n; i++) {
//            if(allowSet(path, row, i)) {//若当前位置允许存放
//                path.put(row, i);
//                dfs(path, location, row + 1, n);
//                path.remove(row);
//            }
//        }
//    }
//    //判断当前位置是否允许存放
//    private boolean allowSet(Map<Integer, Integer> path, int row, int col) {
//        //对角线对角线：和相等或之差相等
//        for(int key : path.keySet()) {
//            if(path.get(key) == col || key + path.get(key) == row + col ||
//                    key - path.get(key) == row - col) {
//                return true;
//            }
//        }
//        return false;
//    }
//    //将位置矩阵转化为真实矩阵
//    private List<List<String>> transLoc(List<Map<Integer, Integer>> location, int n) {
//        List<List<String>> ret = new ArrayList<>();
//        for(int a = 0; a < location.size(); a++) {//对应每一个矩阵
//            for(int key : location.get(a).keySet()) {//对应单独矩阵
//                List<String> list = new ArrayList<>();
//                for(int i = 0; i < n; i++) {
//                    for(int j = 0; j < n; j++) {
//                        if(i == key && j == location.get(a).get(key)) {
//                            list.set(i, list.get(i) + "Q");
//                        } else {
//                            list.set(i, list.get(i) + ".");
//                        }
//                    }
//                }
//                ret.add(list);
//            }
//        }
//        return ret;
//    }
//    public List<List<String>> solveNQueens(int n) {
//        //用一个位置矩阵来记录每一种可能的方案 //        List<Map<Integer, Integer>> location = new ArrayList<>();//位置矩阵
//        Map<Integer, Integer> path = new HashMap();
//        dfs(path, location,  0, n);
//        return transLoc(location, n);
//    }
//    //4.n皇后(dfs + 回溯)
//    private void dfs(List<List<Pair<Integer, Integer>>> allRet,
//                     List<Pair<Integer, Integer>> curRet, int row, int n) {
//        if(row == n) {
//            //一个矩阵的位置以及都出来了，可以放入
//            allRet.add(new ArrayList<>(curRet));
//            return;
//        }
//        for(int i = 0; i < n; i++) {
//            if(allowSet(curRet, row, i)) {//判断是否是否有冲突
//                //没有冲突
//                curRet.add(new Pair<>(row, i));
//                dfs(allRet, curRet, row + 1, n);
//                curRet.remove(curRet.size() - 1);
//            }
//        }
//    }
//    private boolean allowSet(List<Pair<Integer, Integer>> curRet, int x, int y) {
//        for(Pair<Integer, Integer> pair : curRet) {
//            //斜线特点: 之和 或者 之差 相等
//            if(pair.getKey() + pair.getValue() == x + y ||
//                    pair.getKey() - pair.getValue() == x - y || pair.getValue() == y) {
//                return false;
//            }
//        }
//        return true;
//    }
//
//    //将位置矩阵转化为真实的矩阵
//    private List<List<String>> change(List<List<Pair<Integer, Integer>>> allRet, int n) {
//        List<List<String>> ret = new ArrayList<>();
//        for(List<Pair<Integer, Integer>> curRet : allRet) {
//            char[][] str = new char[n][n];
//            //初始化str全为.
//            for(int i = 0; i < n; i++) {
//                for(int j = 0; j < n; j++) {
//                    str[i][j] = '.';
//                }
//            }
//            for(Pair<Integer, Integer> pos : curRet) {
//                str[pos.getKey()][pos.getValue()] = 'Q';
//            }
//            //将char[][]构造成一个List<String>对象
//            ret.add(builderList(str));
//        }
//        return ret;
//    }
//    private List<String> builderList(char[][] str) {
//        List<String> list = new ArrayList<>();
//        for(char[] s : str) {
//            list.add(String.valueOf(s));
//        }
//        return list;
//    }
//
//
//    public List<List<String>> solveNQueens(int n) {
//        List<List<Pair<Integer, Integer>>> allRet = new ArrayList<>();
//        List<Pair<Integer, Integer>> curRet = new ArrayList<>();
//        dfs(allRet, curRet, 0, n);
//        return change(allRet, n);
//    }
//5.n皇后(II)
//    private void dfs(List<Pair<Integer, Integer>> curRet, int row, int n) {
//        for(int i = 0; i < n; i++) {
//            if(row == n) {
//                sum++;
//                return;
//            }
//            //先看是否有冲突
//            if(isCanSet(curRet, row, i)) {
//                //可以放置
//                curRet.add(new Pair<>(row, i));
//                //寻找下一个
//                dfs(curRet, row + 1, n);
//                //去重
//                curRet.remove(curRet.size() - 1);
//            }
//        }
//    }
//    private boolean isCanSet(List<Pair<Integer, Integer>> curRet, int x, int y) {
//        //拿出每一种可能的结果
//        for(Pair<Integer, Integer> pair : curRet) {
//            if(pair.getKey() + pair.getValue() == x + y ||
//            pair.getKey() - pair.getValue() == x - y || pair.getValue() == y) {
//                return false;
//            }
//        }
//        return true;
//    }
//    private int sum;
//    public int totalNQueens(int n) {
//        List<Pair<Integer, Integer>> curRow = new ArrayList<>();
//        dfs(curRow, 0, n);
//        return sum;
//    }
    //6.二叉树的层序遍历(bfs)
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            while(size > 0) {
                Node node = queue.poll();
                for(int i = 0; i < node.children.size(); i++) {
                    queue.offer(node.children.get(i));
                }
                list.add(node.val);
                size--;
            }
            ret.add(list);
        }
        return ret;
    }
    //7.腐烂的橘子
//    值 0 代表空单元格；
//    值 1 代表新鲜橘子；
//    值 2 代表腐烂的橘子。
    public int orangesRotting(int[][] grid) {
        //先找到所有腐烂的橘子，都放入到一个队列中
        int sum = 0;
        Queue<Pair<Integer, Integer>> queue = new LinkedList<>();
        int row = grid.length;
        int col = grid[0].length;
        int cut = 0;//统计新鲜橘子的数量
        for(int i = 0; i < row; i++) {
            for(int j = 0; j < col; j++) {
                if(grid[i][j] == 2) {
                    queue.offer(new Pair<>(i, j));
                } else if(grid[i][j] == 1) {
                    cut++;
                }
            }
        }
        //bfs
        while(!queue.isEmpty() && cut > 0) {
            int size = queue.size();
            sum++;
            while(size > 0) {
                Pair<Integer, Integer> pair = queue.poll();
                int x = pair.getKey();
                int y = pair.getValue();
                //上下左右都要查看一遍，放过的就不用放了
                if(x - 1 >= 0 && grid[x - 1][y] == 1) {//上
                    cut--;//每烂掉一个橘子就减一
                    grid[x - 1][y] = 2;
                    queue.offer(new Pair<>(x - 1, y));
                }
                if(x + 1 < row && grid[x + 1][y] == 1) {//下
                    cut--;//每烂掉一个橘子就减一
                    grid[x + 1][y] = 2;
                    queue.offer(new Pair<>(x + 1, y));
                }
                if(y - 1 >= 0 && grid[x][y - 1] == 1) {//左
                    cut--;
                    grid[x][y - 1] = 2;
                    queue.offer(new Pair<>(x, y - 1));
                }
                if(y + 1 < col && grid[x][y + 1] == 1) {//右
                    cut--;
                    grid[x][y + 1] = 2;
                    queue.offer(new Pair<>(x, y + 1));
                }
                size--;
            }
        }
        return cut == 0 ? sum : -1;
    }
    //8.单词搜索(dfs + 回溯)
    private void dfs(char[][] board, String word, boolean[][] path, int x, int y, int index) {
        if(x < 0 || x >= row || y < 0 || y >= col || path[x][y] || flag) {
            return;
        }
        if(index == word.length()) {
            flag = true;
            return;
        }
        if(board[x][y] == word.charAt(index)) {
            path[x][y] = true;
            dfs(board, word, path, x - 1, y, index + 1);
            dfs(board, word, path, x + 1, y, index + 1);
            dfs(board, word, path, x, y - 1, index + 1);
            dfs(board, word, path, x, y + 1, index + 1);
            path[x][y] = false;
        }
    }


    private int row;
    private int col;
    private boolean flag;
    public boolean exist(char[][] board, String word) {
        this.row = board.length;
        this.col = board[0].length;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                int index = 0;
                boolean[][] path = new boolean[row][col];//表示当前走过的路径
                dfs(board, word, path, i, j, index);
                if(flag) {
                    return true;
                }
            }
        }
        return false;
    }
    //8.字母异位词分组(HashMap)
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, ArrayList<String>> map = new HashMap<>();
        for(int i = 0; i < strs.length; i++) {
            char[] str = strs[i].toCharArray();
            Arrays.sort(str);
            String s = String.valueOf(str);
            if(!map.containsKey(s)) {
                map.put(s, new ArrayList<>());
            }
            map.get(s).add(strs[i]);
        }
        return new ArrayList<>(map.values());
    }
    //9.比特位计数(暴力)
    public int[] countBits(int n) {
        int[] ret = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            //拿到每一位数字
            int num = i;
            int count = 0;
            while(num > 0) {
                if((num & 1) == 1) {
                    count++;
                }
                num >>= 1;
            }
            ret[i] = count;
        }
        return ret;
    }
//    //动态规划(优化)
//    public int[] countBits(int n) {
//        int[] ret = new int[n + 1];
//        for(int i = 1; i <= n; i++) {
//            if(i % 2 == 1) {
//                ret[i] = ret[i - 1] + 1;
//            } else {
//                ret[i] = ret[i / 2];
//            }
//        }
//        return ret;
//    }
    //10.完全平方数(动态规划)
    public int numSquares(int n) {
        if(n == 1 || n ==2 || n == 3) {
            return n;
        }
        int[] dp = new int[n + 1];
        Arrays.fill(dp, n);//最多的完全平方数组合就是全一
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= Math.sqrt(i); j++) {
                dp[i] = Math.min(dp[i], dp[i - j*j] + 1);
            }
        }
        return dp[n];
    }
    //零钱兑换(未完)
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for(int i = 0; i < coins.length; i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }

        }
        if(dp[amount] == Integer.MAX_VALUE) {
            dp[amount] = -1;
        }
        return dp[amount];
    }


}
class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.numSquares(13);
    }
}
